# 代码编写者： 李朔
# 开发时间： 2021/9/12 10:48
'''
代码效果很差，非常不建议学习菜鸟教程上的代码，代码可读性差，并且对算法的利用率很低，会造成很多额外的开支
'''

arr=[50,45,40,20,25,35,30,10,15]
def Heapify(arr,n,i):
    '''
    :param arr: 待排序序列
    :param n: 待排序序列大小
    :param i:
    :return:
    '''
    #根堆调整-根堆构建
    largest=i
    l=2*i+1   #左孩子结点 left=2*i+1
    r=2*i+2   #右孩子结点 right=2*i+2
    print("l:{0},r:{1}".format(l,r))
    #从第一个非叶子结点开始比较
    if l<n and arr[i]<arr[l]:
        #存在该叶子结点，且其父节点的value小于左叶子结点的value值
        largest=l
    if r<n and arr[largest]<arr[r]:
        largest=r
    if largest!=i:
        #证明要发生交换，需要进行结点调整
        arr[i],arr[largest]=arr[largest],arr[i]  #交换
        Heapify(arr,n,largest)
def HeapSort(arr):
    #堆排序算法
    n=len(arr)   #待排序序列大小
    #创建一个MaxHeap
    print("初始根堆构建----------")
    for i in range(n,-1,-1):  #9-8-7-6-5-4-3-2-1-0
        print("第i:{0}轮".format(i))
        Heapify(arr,n,i)
    #一个个交换元素
    for i in range(n-1,0,-1):
        arr[i],arr[0]=arr[0],arr[i]
        Heapify(arr,i,0)

HeapSort(arr)
print(arr)